题目

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

输入: [10,2]
输出: "102"

解答

可以认为在拼接时，每个数字都有一个权重，把权重小的放在前面会使得拼接结果更小。那么实质上就是一个排序问题。关键在于如何确定这个权重，或者说如何确定排序规则。

  1. 两个数 x、y，若 xy < yx，那么 x 的权重更小，在最后的结果中应该放在 y 的前面；

  2. 如 xy < yx, yz < zy，容易证明有 xz < xz，也即传递性。

实现

使用标准库的 sort 函数，自定义匿名比较函数。
其中排序规则，可以根据数值大小比较也可以根据字符串字典序比较。

或者最好自己实现快排。

注意在比较大小时，计算数值比较麻烦，也可以直接转换为字符串然后比较字典序。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string minNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), [](int a, int b) -> bool {
            // 数值大小比较
            int as = a < 10 ? 1 : (int)log10(a) + 1; // a的位数
            int bs = b < 10 ? 1 : (int)log10(b) + 1; // b的位数
            return a*pow(10, bs) + b < b*pow(10, as) + a;

            // 字符串字典序比较
            // string as = to_string(a);
            // string bs = to_string(b);
            // return as+bs < bs+as;
        });
        stringstream ss;
        for(auto num : nums){
            ss << num;
        }
        return ss.str();
    }
};

复杂度

  • 时间复杂度 O(NlogN) ：stl sort 使用快排的平均时间复杂度
  • 空间复杂度 O(1)